Лемма о частных решениях

Многочлен $\chi(x) = x^k - a_1 x^{k-1} - \dots - a_{k-1}x - a_k$ называется **характеристическим многочленом** рекуррентного соотношения $f(n) = a_1 f(n-1) + \dots + a_k f(n-k)$

Пусть $\lambda \neq 0$. Функция $f(n) = \lambda^n$ является решением рекуррентного соотношения $f(n) = a_1 f(n-1) + \dots + a_k f(n-k)$ тогда и только тогда, когда $\lambda$ — корень $\chi(x)$.

При $\lambda \neq 0$: $$\lambda^n = a_1 \lambda^{n-1} + \dots + a_k \lambda^{n-k} \iff \lambda^k = a_1 \lambda^{k-1} + \dots + a_k \iff \lambda \text{ — корень } \chi(x)$$ $\square$